public class MergeSort {
    //一道归并排序的经典题目, 复习了一下归并排序
    //https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=295&tqId=23260&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    static int[] tmp;
    static int INF;
    public int InversePairs (int[] nums) {
        // write code here
        tmp = new int[nums.length];
        //别忘记模INF
        INF = (int)1e9 + 7;
        return mergeSort(nums,0,nums.length - 1);
    }


    private static int mergeSort(int[] nums,int left ,int right){
        //只有一个元素或者mid + 1导致越界
        if(left >= right){
            return 0;
        }
        int ret = 0;
        int mid = (left + right) / 2;
        //归并分块[left, mid]  [mid + 1, right]
        //递归取左边里面的逆序对个数, 取右边里面的逆序对个数
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid + 1, right);
        //左边是有序数组, 右边也是有序数组
        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;
        //排序有序数组
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] > nums[cur2]){
                //比如 5,7,9     4,6
                //如果5比4大, 那5后面的都比4大
                ret += mid - cur1 + 1;
                //防止溢出
                ret %= INF;
                tmp[i++] = nums[cur2++];
            }else{
                tmp[i++] = nums[cur1++];
            }
        }
        //剩下的丢到数组里
        while(cur1 <= mid){
            tmp[i++] = nums[cur1++];
        }
        while(cur2 <= right){
            tmp[i++] = nums[cur2++];

        }
        //将数组写回原数组
        for(int j = left;j <= right;j++){
            nums[j] = tmp[j - left];
        }
        return ret;
    }
    public static void main(String[] args) {

    }
}
